package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

import java.util.Arrays;

public class TwoSum {


    public static void main(String [] args){
        int MAX=1000000;
        int N=100000;
        final int[] a=new int[N];
        for (int i=0;i<N;i++){
            a[i]=StdRandom.uniform(-MAX,MAX);
        }
        new Thread(new Runnable() {
            @Override
            public void run() {
                Stopwatch stopwatch=new Stopwatch();
                StdOut.println("count:"+twoSum(a));
                StdOut.println(stopwatch.elapseTime());//5.2s
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                Stopwatch stopwatch2=new Stopwatch();
                StdOut.println("count:"+twoSumFast(a));
                StdOut.println(stopwatch2.elapseTime());//0.05s
            }
        }).start();

    }

    /**
     * 时间复杂度   N^2
     * @param a
     * @return
     */
    public static int  twoSum(int[] a){
        int count=0;
        for (int i=0;i<a.length;i++){
            for (int j=i+1;j<a.length;j++){
                if (a[i]+a[j]==0){
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 时间复杂度  NlogN
     * @param a
     * @return
     */
    public static int twoSumFast(int[] a){
        int count=0;
        Arrays.sort(a);//归并排序  NlogN

        for (int i=0;i<a.length;i++){
            if (BinarySearch.rank(-a[i],a)>i){
                count++;
            }
        }
        return count;
    }

    /**
     * 线性级别 ~N
     * 由于数组已经排序（从小到大），负数在左侧，正数在右侧。
     * TwoSumFaster
     * 设最左侧下标为 lo，最右侧下标为 hi。
     * 如果 a[lo] + a[hi] > 0, 说明正数太大，hi--。
     * 如果 a[lo] + a[hi] < 0，说明负数太小，lo++。
     * 否则就找到了一对和为零的整数对，lo++, hi--。
     * @param sortedArray
     * @return
     */
    public static int twoSumFastSorted(int[] sortedArray){
        int count = 0;
        int N=sortedArray.length;
        int lo=0;
        int hi=N-1;
        while (lo<hi){
            if (sortedArray[lo]+sortedArray[hi]>0){
                hi--;
            }else if (sortedArray[lo]+sortedArray[hi]<0){
                lo++;
            }else {
                count++;
                lo++;
                hi--;
            }
        }
        return count;
    }

}
